package other;

import javax.swing.plaf.synth.SynthSpinnerUI;
import java.util.logging.Level;

/**
 * 二分查找 优点 比较次数少，查找次数快 缺点 要求二分查找的集合或者数组是有序的
 */
public class BinarySearch {

  /**
   * 递归实现二分查找
   */
  public int binarySearch(int[] array, int key, int low, int high) {
    if (array == null || array.length <= 0) {
      return -1;
    }

    if (key < array[low] || key > array[high] || low > high) {
      return -1;
    }
    int mid = (low + high) / 2;
    if (array[mid] == key) {
      return mid;
    } else if (array[mid] < key) {
      return binarySearch(array, key, mid + 1, high);
    } else {
      return binarySearch(array, key, low, mid - 1);
    }
  }


  public int binarySearch2(int[] array, int key) {
    int low = 0;
    int high = array.length - 1;
    if (array == null || array.length <= 0) {
      return -1;
    }

    if (key < array[low] || key > array[high]) {
      return -1;
    }
    int mid = 0;
    while (low <= high) {
      mid = (low + high) / 2;
      if (array[mid] == key) {
        return mid;
      } else if (array[mid] > key) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return -1;
  }


  public static void main(String args[]) {
    BinarySearch binarySearch = new BinarySearch();
    int[] array = new int[]{1, 3, 5, 7, 9, 12, 43, 44, 54};
//        int index=binarySearch.binarySearch(array,9,0,array.length-1);
    int index = binarySearch.binarySearch2(array, 14);
    if (index != -1) {
      System.out.println(array[index]);
    } else {
      System.out.println("数组中不存在要查找的数字");
    }
  }
}
